package week5;

/**
 *
 *
 * 1143. 最长公共子序列
 * https://leetcode-cn.com/problems/longest-common-subsequence/
 *
 * 执行结果：
 * 通过
 * 显示详情
 *
 * 添加备注
 * 执行用时：8 ms, 在所有 Java 提交中击败了89.88% 的用户
 * 内存消耗：42.1 MB, 在所有 Java 提交中击败了34.30% 的用户
 * 通过测试用例：44 / 44
 *
 *
 */
public class Week5LongestCommonSubsequence {

    public int longestCommonSubsequence(String text1, String text2) {
        int length1 = text1.length();
        int length2 = text2.length();

        int[][] dynamicPlan = new int[length1 + 1][length2 + 1];
        for(int f1 = 1; f1 <= length1; f1++) {
            char c1 = text1.charAt(f1 - 1);
            for(int f2 = 1; f2 <= length2; f2++) {
                char c2 = text2.charAt(f2 - 1);
                if(c1 == c2) {
                    dynamicPlan[f1][f2] = dynamicPlan[f1 - 1][f2 - 1] + 1;
                } else {
                    dynamicPlan[f1][f2] = Math.max(dynamicPlan[f1 - 1][f2], dynamicPlan[f1][f2 - 1]);
                }
            }
        }

        return dynamicPlan[length1][length2];
    }
}
